package com.chenken.recursion;

/**
 * 斐波拉契数列
 * 1,1,2,3,5,8,13,21,34......
 */
public class Fib {

	/**
	 * 第一种
	 * @param n
	 * @return
	 */
	public int fib1(int n) {
		if(n <= 2) return 1;
		return fib1(n-1) + fib1(n-2);
	}
	
	/**
	 * 第二种
	 * @param n
	 * @return
	 */
	public int fib2(int n) {
		if(n <= 2) return 1;
		int[] array  = new int[n+1];
		array[1] = array[2] = 1;
		return fib2(n,array);
	}
	
	private int fib2(int n,int[] array) {
		if(array[n] == 0) {
			array[n] = fib2(n-1,array) + fib2(n-2,array);
		}
		return array[n];
	}
	
	/**
	 * 第三种
	 * @param n
	 * @return
	 */
	int fib3(int n) {
		if(n <= 2) return 1;
		return fib1(n-1) + fib1(n-2);
	}
	
	/**
	 * 第四种
	 * @param n
	 * @return
	 */
	int fib4(int n) {
		if(n <= 2) return n;
		int first = 1;
		int second = 1;
		for(int i = 3;i<=n;i++) {
			second = first + second;
			first = second - first;
		}
		return second;
	}
	
}
